package leetcode;

import com.sun.org.apache.xalan.internal.xsltc.compiler.util.StringStack;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class GenerateParenthesis {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<String> res = new GenerateParenthesis().generateParenthesis(n);
        System.out.println(res);
    }

    public List<String> generateParenthesis(int n){
        List<String> all = new ArrayList<>();
        char[] allChar = new char[2 * n];
        //generateAll(all, n, new StringBuilder());
        generateAll(allChar, 0, all);
        return all;
    }

    private void generateAll(List<String> all, int n, StringBuilder builder){
        if(builder.length() == 2 * n){
            String str = builder.toString();
            if(isValid(str)){
                all.add(str);
            }
            return;
        }
        StringBuilder builder1 = new StringBuilder(builder);
        generateAll(all, n, builder1.append("("));
        StringBuilder builder2 = new StringBuilder(builder);
        generateAll(all, n, builder2.append(")"));
    }

    private void generateAll(char[] arr, int pos, List<String> all){
        if(pos == arr.length){
            String str = new String(arr);
            if(isValid(str)){
                all.add(str);
            }
            return;
        }
        arr[pos] = '(';
        generateAll(arr, pos + 1, all);
        arr[pos] = ')';
        generateAll(arr, pos + 1, all);
    }

    private boolean isValid(String str){
        Stack<Character> s = new Stack<>();
        for(char item: str.toCharArray()){
            switch (item){
                case '(':
                    s.push(item);
                    break;
                case ')':
                    if(s.isEmpty()){
                        return false;
                    }else{
                        char last = s.pop();
                        if(last == ')'){
                            return false;
                        }
                    }
                    break;
            }
        }
        return s.isEmpty();
    }
}
